package study.datastructure.queue.impl;

import study.datastructure.queue.Deque;

import java.util.Iterator;

public class CircularArrayDeque<E> implements Deque<E>, Iterable<E> {
    private E[] elements;
    private int head; // 头指针
    private int tail; // 尾指针
    private int size; // 当前队列大小
    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    @SuppressWarnings("unchecked")
    public CircularArrayDeque() {
        elements = (E[]) new Object[DEFAULT_CAPACITY]; // 初始化数组
        head = 0;
        tail = 0;
        size = 0;
    }

    private int nextIndex(int index) {
        return (index + 1) % elements.length; // 计算下一个索引，支持循环
    }

    private int prevIndex(int index) {
        return (index - 1 + elements.length) % elements.length; // 计算上一个索引，支持循环
    }

    @Override
    public boolean offerFirst(E e) {
        if (e == null) throw new IllegalArgumentException("Element cannot be null");
        if (isFull()) resize(); // 检查是否需要扩容

        head = prevIndex(head); // 先移动头指针
        elements[head] = e; // 添加元素
        size++;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (e == null) throw new IllegalArgumentException("Element cannot be null");
        if (isFull()) resize(); // 检查是否需要扩容

        elements[tail] = e; // 添加元素
        tail = nextIndex(tail); // 移动尾指针
        size++;
        return true;
    }

    @Override
    public E pollFirst() {
        if (isEmpty()) return null; // 空队列，返回 null
        E value = elements[head]; // 获取头部元素
        elements[head] = null; // 清除头部元素的引用以帮助 GC
        head = nextIndex(head); // 移动头指针
        size--;
        return value; // 返回头部元素
    }

    @Override
    public E pollLast() {
        if (isEmpty()) return null; // 空队列，返回 null
        tail = prevIndex(tail); // 移动尾指针
        E value = elements[tail]; // 获取尾部元素
        elements[tail] = null; // 清除尾部元素的引用以帮助 GC
        size--;
        return value; // 返回尾部元素
    }

    @Override
    public E peekFirst() {
        return isEmpty() ? null : elements[head]; // 返回头部元素但不删除
    }

    @Override
    public E peekLast() {
        return isEmpty() ? null : elements[prevIndex(tail)]; // 返回尾部元素但不删除
    }

    @Override
    public boolean isEmpty() {
        return size == 0; // 判断队列是否为空
    }

    @Override
    public boolean isFull() {
        return size == elements.length; // 判断队列是否已满
    }

    private void resize() {
        @SuppressWarnings("unchecked")
        E[] newArray = (E[]) new Object[elements.length * 2]; // 新建一个更大的数组
        int currentIndex = head;

        // 复制现有元素到新数组
        for (int i = 0; i < size; i++) {
            newArray[i] = elements[currentIndex];
            currentIndex = nextIndex(currentIndex);
        }
        elements = newArray; // 更新数组引用
        head = 0; // 头指针重置
        tail = size; // 尾指针设置到新数组的末尾
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int current = head;
            int count = 0; // 计数，确保不超过元素数量

            @Override
            public boolean hasNext() {
                return count < size; // 判断是否还有下一个元素
            }

            @Override
            public E next() {
                E value = elements[current]; // 获取当前元素
                current = nextIndex(current); // 移动到下一个元素
                count++;
                return value; // 返回当前元素
            }
        };
    }
}
